This case involves a protracted dispute between Arizona Public Service Company ("APS") and the Navajo Nation over whether the Navajo Nation can regulate certain APS employment policies affecting the hiring of Navajos who wish to work in APS's Four Corners Power Plant. The plant is operated on tribal trust land in northwestern New Mexico that APS leased from the Navajo Nation in agreements that required the Department of Interior's approval. See 25 U.S.C. § 415 (providing for the Secretary of Interior's approval of Indian leases). The plant is owned by a consortium of utility companies and is run by APS.

After the Navajo Nation Supreme Court ruled that APS's anti-nepotism policy violated the Navajo employment discrimination laws, APS filed this suit in district court against Navajo officials challenging the Navajo Nation's authority to regulate APS's employment policies at the plant. APS chiefly contended that the Navajo Nation had waived its right to regulate employment practices at the plant pursuant to the express terms of leases executed prior to the enactment of the Navajo law at issue, the Navajo Preference in Employment Act (NPEA), 15 Navajo Trib.Code (NTC) §§ 601 et seq. (1985). The district court agreed and entered judgment for APS.

The Navajo officials appeal, challenging federal court jurisdiction as well as the validity of any waiver of Navajo authority to regulate APS. APS cross-appeals, seeking the same result on other legal theories. Because we affirm on the grounds relied upon by the district court, we need not decide all the issues raised in the cross-appeal. We have jurisdiction pursuant to 28 U.S.C. § 1291.

The rights and duties of APS and the Navajo Nation are set forth in the original lease agreement, executed in 1960, and two subsequent amendments executed in 1966 and 1985 (collectively, "Lease Documents").1 All of the Lease Documents were signed by the parties and approved by the Secretary of the Interior (the "Secretary").

The principal relevant clause of the 1960 Lease is the Operations Clause, § 17, which contains the following non-regulation covenant ("Non-Regulation Covenant"):

The Tribe covenants that, other than as expressly set out in this agreement, it will not directly or indirectly regulate or attempt to regulate the Company or the construction, maintenance or operation of the power plant and transmission system by the Company, or its rates, charges, operating practices, procedures, safety rules or other policies or practices.

The Non-Regulation Covenant was not materially changed by way of the 1966 or 1985 amendments. The 1960 Lease also provided in Section 19 that "[APS] agrees that in selecting applicants for employment on the Reservation, it will employ Navajo Indians when available in all positions for which they are qualified in the judgment of the Company, and will pay prevailing wages to such Navajo employees." Additionally, the 1960 Lease established a general dispute resolution process providing that the Secretary would resolve disputes arising out of the Lease. The 1966 amendment reiterated the Navajo preference and non-regulation provisions, and again provided for the Secretary's involvement in the resolution of disputes.

The 1985 amendment once again provided for the preferential employment of Indians.2 The amendment incorporated a letter agreement ("Letter Agreement") that explained the preferences in more detail.3 The Letter Agreement also provided for the establishment of a compulsory minitrial mechanism in the event of a dispute arising out of the Letter Agreement.4

Shortly after approval of the 1985 amendment and the Letter Agreement, the Navajo Nation enacted the NPEA. The NPEA, passed "[t]o protect the health, safety, and welfare of Navajo workers," NTC § 602(a)(6), vests Navajos and their spouses with broad substantive rights against employees and non-Navajo workers. It expressly requires employers to exercise preferential hiring practices in favor of Navajos.

On October 24, 1986, the Office of Navajo Labor Relations ("ONLR") initiated proceedings before the Navajo Labor Relations Board ("NLRB"), contending that the NPEA prohibited APS from applying its anti-nepotism policy to Navajo employees and applicants at the plant. APS invoked the dispute resolution provisions of the Lease Documents, requiring arbitration before the Secretary, but the Navajo Nation refused to participate. On February 9, 1987, the NLRB awarded relief to the individuals allegedly harmed, held that APS's anti-nepotism policy was null and void because it violated the NPEA, and permanently enjoined APS from enforcing its policy at the plant.

APS appealed the NLRB's decision to the Navajo Nation Supreme Court on Feb. 19, 1987. The parties settled the individual claims, and on May 26, 1988, the Navajo Nation Supreme Court affirmed the NLRB's decision. See Arizona Public Service Co. v. Office of Navajo Labor Relations, 17 ILR 6105, 6105 (Navajo S.Ct. 1990). The court held that the Navajo Nation has power to regulate the labor relations of non-Indian businesses within the reservation; that neither federal law nor prior contracts or agreements preempt Navajo law, because the Navajo Nation, as a sovereign power, retains its police power to protect the health, welfare and safety of its citizens; and that APS's anti-nepotism policy violated the NPEA by discriminating on the basis of marital status. See id. at 6109-15; NTC § 604B.7 (mandating that all employers shall use non-discriminatory job qualifications and selection criteria in employment).

APS then filed this action for declaratory and injunctive relief in the district court. APS's amended complaint sought relief on four grounds: 1) enforcement of the NPEA was preempted by federal law; 2) the specific terms of the Lease Documents and Grants prohibited application of Navajo labor law at the plant; 3) the Navajo Nation's threatened enforcement action against APS exceeded its proper jurisdiction; and 4) the hearing before the ONLR was violative of APS's due process rights under the federal Constitution and the Indian Civil Rights Act, 25 U.S.C. §§ 1301 et seq.

The district court disposed of all the parties' contentions in three orders dated December 10, 1991, October 9, 1992 and September 30, 1993. The district court dismissed APS's first and fourth claims. The district court found it had federal question jurisdiction over the second claim, and that while the Navajo Nation and its governing agencies5 were immune from suit, tribal officials were not. On the merits, the district court concluded that the Navajo Nation waived its power to regulate employment of the plan in clear and unmistakable terms, precluding resort to parol evidence. The district court permanently enjoined the defendants from attempting to regulate APS's "employment relations policies or practices at the Four Corners Power Plant as they relate to the employment of Indians," and permanently enjoined the application of the NPEA in the same context. The district court also entered judgment on the merits in favor of the defendants on APS's third claim. This appeal followed.

The Navajo appellants' threshold contention in this appeal is that the district court lacked subject matter jurisdiction over APS's claim that the Navajo Nation committed in the Lease Documents that it would not regulate APS's operation of the Four Corners Power Plant. We review a district court's determination of federal question jurisdiction de novo, but we accept the district court's factual findings on jurisdictional issues unless clearly erroneous. Stock West, Inc. v. Confederated Tribes, 873 F.2d 1221, 1225 (9th Cir.1989). We also review de novo the scope of a tribe's ability to regulate or adjudicate matters affecting non-Indians. United States ex rel. Morongo Band of Mission Indians v. Rose, 34 F.3d 901, 905 (9th Cir.1994); FMC v. Shoshone-Bannock Tribes, 905 F.2d 1311, 1313-14 (9th Cir.1990), cert. denied, 499 U.S. 943, 111 S. Ct. 1404, 113 L. Ed. 2d 459 (1991). The Navajo Nation contends that the issue is one of tribal contract law that has already been resolved in the Navajo Nation Supreme Court and may not be adjudicated in federal court. We view the issue, however, as to what extent the Navajo Nation can apply tribal law to regulate the activities of a non-Indian. The Supreme Court has squarely held that such an issue raises a question of federal common law. National Farmers Union Ins. Cos. v. Crow Tribe (National Farmers ), 471 U.S. 845, 105 S. Ct. 2447, 85 L. Ed. 2d 818 (1985).

In National Farmers, the Supreme Court held that a federal court is empowered to determine under 28 U.S.C. § 1331 whether a tribal court has exceeded the lawful limits of its jurisdiction. National Farmers, 471 U.S. at 853, 105 S.Ct. at 2452. The Court wrote: "The question whether an Indian tribe retains the power to compel a non-Indian property owner to submit to the civil jurisdiction of a tribal court is one that must be answered by reference to federal law and is a 'federal question' under § 1331." Id. at 852, 105 S.Ct. at 2452. The issue in this case is whether the Navajo Nation retained its power to regulate the affairs of a non-Indian lessee, a question whose federal nature is the same in all material respects as the question National Farmers posed in regard to property owners.

This conclusion is compelled by decisions following National Farmers in which we have expressly held that a non-Indian challenging an exercise of tribal adjudicatory or legislative power states a claim that arises under federal law. See, e.g., Chilkat Indian Village v. Johnson, 870 F.2d 1469, 1473, 1475 n. 10 (9th Cir.1989). In the case at bar, APS challenges the Navajo Nation's application of both its legislative and adjudicatory power. See also United States ex rel. Morongo Band of Mission Indians v. Rose, 34 F.3d 901, 905 (9th Cir.1994) (United States ex rel. Morongo ) ("Tribal jurisdiction over non-Indians is a question of federal law reviewed de novo."); Imperial Granite Co. v. Pala Band of Mission Indians, 940 F.2d 1269, 1272, and n. 5 (9th Cir.1991) (noting that a National Farmers review requires a colorable claim that a tribe's action exceeded its powers under federal law); FMC v. Shoshone-Bannock Tribes, 905 F.2d 1311, 1314 (9th Cir.1990), cert. denied, 499 U.S. 943, 111 S. Ct. 1404, 113 L. Ed. 2d 459 (1991) (question of tribal court jurisdiction is a federal question).

The federal texture of an inquiry into a tribe's authority over a non-member can be explained by the historical evolution of Indian authority: "At one time [tribes] exercised virtually unlimited power over their own members as well as those who were permitted to join their communities. Today, however, the power of the federal government over the Indian tribes is plenary." National Farmers, 471 U.S. at 851, 105 S.Ct. at 2451.

The Navajo officials nevertheless insist that this dispute raises no federal question, and urge that Littell v. Nakai, 344 F.2d 486, 488 (9th Cir.1965), cert. denied, 382 U.S. 986, 86 S. Ct. 531, 15 L. Ed. 2d 474 (1966), is somehow dispositive of the jurisdictional issue. In Littell, we held that the mere fact that a contract has been authorized by federal law and approved by federal officials does not necessarily confer federal jurisdiction. Id. Littell involved a tortious interference of contract suit brought by the General Counsel of the Navajo Tribe against the Chairman of the Navajo Tribal Council. Affirming the district court's dismissal for lack of jurisdiction, this court found that the gist of the dispute centered on the contract and its construction rather than the fact that the contract was approved pursuant to federal statute. Id. at 488-90.

Littell was, of course, decided nearly twenty years before National Farmers, and involved a distinctly tribal issue, i.e., the internal government operations of a tribe. In contradistinction to Littell, however, here, as in National Farmers, we address the federal issue of a tribe's authority to regulate the conduct of a non-Indian in an activity having nothing to do with tribal governance: the leasing of Navajo land for a purely commercial operation. Additionally, we note that while Littell held that the requirement for federal approval of leases between tribes and non-Indians was not dispositive of the federal question issue, the requirement of federal approval is nonetheless highly probative where the gravamen of a dispute does not concern tribal self-governance.

In contending that this is simply a contractual dispute arising under tribal law, appellants rely upon Morongo Band of Indians v. California St. Bd. of Equalization, 858 F.2d 1376 (9th Cir.1988), cert. denied, 488 U.S. 1006, 109 S. Ct. 787, 102 L. Ed. 2d 779 (1989), and Gila River Indian Community v. Henningson, Durham & Richardson, 626 F.2d 708 (9th Cir.1980), cert. denied, 451 U.S. 911, 101 S. Ct. 1983, 68 L. Ed. 2d 301 (1981). Neither is helpful.

In Morongo an Indian tribe had leased trust land from a tribe member who owed taxes to the State of California. The lease was never approved by the Secretary of the Interior. When the state levied on the money the Tribe was to pay the landlord as rent, the Tribe filed an interpleader action in federal court asking the court to decide whether the rental payments should be paid to the landlord or to the state. Our court held that the interpleader statute does not itself confer federal question jurisdiction, and that the district court lacked subject matter jurisdiction. Id. at 1381-82, 1386. Because the Tribe made no claim to the funds, there was no issue whatsoever concerning the extent to which the Tribe could regulate the affairs of non-Indians. For that reason, the case contained no National Farmers issue of federal law.

Similarly, Gila River is inapposite. Gila River, decided before National Farmers, involved a suit for damages by a tribe against non-Indian designers of a building on the reservation. Gila River, 626 F.2d at 709. We found jurisdiction lacking under § 1331 because we held that commercial agreements between tribes and state governments should be governed by state law. Id. at 715. Gila River involved no National Farmers inquiry.

As a final jurisdictional contention, appellees argue that they enjoy sovereign immunity from suit. See Chemehuevi Indian Tribe v. California St. Bd. of Equalization, 757 F.2d 1047, 1051 (9th Cir.), rev'd in part on other grounds, 474 U.S. 9, 106 S. Ct. 289, 88 L. Ed. 2d 9 (1985) (noting that question of tribal sovereign immunity is jurisdictional in nature). Indian tribes may not be sued absent an express and unequivocal waiver of immunity by the tribe or abrogation of tribal immunity of Congress. See Burlington Northern R.R. Co. v. Blackfeet Tribe, 924 F.2d 899, 901 (9th Cir.1991), cert. denied, 505 U.S. 1212, 112 S. Ct. 3013, 120 L. Ed. 2d 887 (1992). Tribal sovereign immunity, however, does not bar a suit for prospective relief against tribal officers allegedly acting in violation of federal law. Id. Here, APS has alleged that certain Navajo officials violated federal law by acting beyond the scope of their authority. See National Farmers, 471 U.S. at 845, 105 S.Ct. at 2448 (noting that in all cases before the Supreme Court involving questions as to the extent to which Indian tribes have retained the power to regulate the affairs of non-Indians, "the governing rule of decision has been provided by federal law"). That is essentially all that this case involves at the present stage. Injunctive relief is sought; damages are not.

National Farmers establishes a prudential rule of exhaustion that has been satisfied in this case. The National Farmers court instructed that while " § 1331 encompasses the federal question whether a tribal court has exceeded the lawful limits of its jurisdiction ... exhaustion is required before such a claim may be entertained in federal court." Id., 471 U.S. at 857, 105 S. Ct. at 2454. Allowing the tribal court to determine, as an issue of first impression, whether it properly has jurisdiction leaves open the possibility that such jurisdiction can later be challenged in federal court. Brendale v. Confederated Yakima Indian Nation, 492 U.S. 408, 427 n. 10, 109 S. Ct. 2994, 3006 n. 10, 106 L. Ed. 2d 343 (1989). Technically, exhaustion is not a jurisdictional prerequisite, but is required as a matter of comity. Iowa Mutual Ins. Co. v. LaPlante (Iowa Mutual), 480 U.S. 9, 16 n. 8, 107 S. Ct. 971, 976 n. 8, 94 L. Ed. 2d 10 (1987).

In this case, the Navajo Nation Supreme Court found that it had jurisdiction over the dispute. See 17 ILR at 6114. Because both the NLRB and the Navajo Nation Supreme Court have considered this dispute, the exhaustion requirement has been met. The Navajo Nation Supreme Court's determination of tribal jurisdiction is thus properly the subject of federal review. See Iowa Mutual, 480 U.S. at 19, 107 S.Ct. at 978. Shoshone-Bannock is not to the contrary. In that case, we noted that under National Farmers, federal courts "have no obligation" to follow a tribal court's determination of its jurisdiction. Shoshone-Bannock, 905 F.2d at 1314. We emphasized: "[F]ederal courts are the final arbiters of federal law, and the question of tribal court jurisdiction is a federal question." Id. We hold under the principles announced in National Farmers that the issue of the tribal authority to regulate a non-Indian issue is a federal question.

II. The Enforceability of the Navajo Ordinance

We turn to the merits of the issue of the enforceability of the ordinance. Initially, APS contends that the Navajo Nation may never exercise its sovereign power to regulate a non-Indian lessee. It relies upon the Supreme Court's recognition of "the general proposition that the inherent powers of an Indian tribe do not extend to the activities of nonmembers of the tribe." Montana v. United States, 450 U.S. 544, 565, 101 S. Ct. 1245, 1258, 67 L. Ed. 2d 493 (1980). Montana, however, was concerned with sovereign power over a non-Indian fee holder, not a lessee. See United States ex rel. Morongo, 34 F.3d at 906 ("Montana ... only established that alienation of lands in fee to non-Indians presumptively divests [Indians] of authority."). Moreover, Montana recognized, even in the fee context, that there are exceptions where contractual relationships exist:

To be sure, Indian tribes retain inherent sovereign power to exercise some forms of civil jurisdiction over non-Indians on their reservations, even on non-Indian fee lands. A tribe may regulate ... the activities of nonmembers who enter consensual relationships with the tribe or its members, through commercial dealing, contracts, leases, or other arrangements.

Id. 450 U.S. at 565, 101 S. Ct. at 1258 (emphasis added) (internal citations omitted).

We need not determine in this case the precise limits of the Navajo Nation's inherent power to regulate employment relations of a non-Indian employer and Indian employees. Assuming arguendo, such authority exists, the dispositive question in this case is whether the Navajo Nation has agreed to a valid waiver of such a right. In Merrion v. Jicarilla Apache Tribe, 455 U.S. 130, 102 S. Ct. 894, 71 L. Ed. 2d 21 (1982), the Supreme Court discussed the differences and similarities among federal, state, local and Indian sovereigns. It held that all these sovereigns can waive sovereign power if they do so in sufficiently clear contractual terms:

Each of these governments has different attributes of sovereignty, which also derive from different sources. These differences, however, do not alter the principles for determining whether any of these governments has waived its sovereign power through contract, and we perceive no principled reason for holding that the different attributes of Indian sovereignty require different treatment in this regard. Without regard to its source, sovereign power, even when unexercised, is an enduring presence that governs all contracts subject to the sovereign jurisdiction, and will remain intact unless surrendered in unmistakable terms.

Id. at 148, 102 S.Ct. at 907.

We agree with the district court that the record evidences the requisite "unmistakable waiver" by the tribal officials concerned. The clear language contained in the Lease Documents, including the Non-regulation Covenant and the subsequent detailed provisions of the Letter Agreement on hiring preferences, demonstrated the parties' understanding that the Navajo Nation would not regulate APS's employment decisions beyond enforcement of the contractual commitments. Of particular significance to us is the parties' establishment of a special dispute resolution mechanism in order to resolve any disputes that might arise in connection with employment matters. See supra note 4. The record in this case reflects that the Navajo Nation refused to abide by the contractual mechanisms and resorted to passage and enforcement of the NPEA in order to bypass them. We thus refuse to disturb the district court's injunction.

The appellants further contend that the Navajo Tribal Council, which approved the operative documents here (and later enacted the NPEA), lacked authority to waive sovereign police power in lease agreements. This position is untenable. As the governing body of the Navajo Nation, the Navajo Tribal Council is similar in function to the Congress of the United States. United States v. Begay, 42 F.3d 486, 490 (9th Cir.1994), cert. denied, --- U.S. ----, 116 S. Ct. 93, 133 L. Ed. 2d 49 (1995). "The legitimacy of the Navajo Tribal Council, the freely elected governing body of the Navajos, is beyond question." Kerr-McGee Corp. v. Navajo Tribe, 471 U.S. 195, 201, 105 S. Ct. 1900, 1904, 85 L. Ed. 2d 200 (1985). Thus, the Navajo Tribal Council had authority to effect a waiver of the Navajo Nation's power to subject a lessee to employment regulations.

AFFIRMED.